import Data.List
import Data.Ord

primes :: Integral a => [a]
primes = 2 : filter ( (==1) . length . primeFactors ) [3,5..]

primeFactors :: Integral a => a -> [a]
primeFactors n = factor n primes
	where
	factor n (p:ps)
		| p*p > n		 = [n]
		| n `mod` p == 0 = p : factor ( n `div` p )	(p:ps)
		| otherwise		 = factor n ps

isPrime :: Integral a => a -> Bool
isPrime n
	| n <= 1 	= False
	| otherwise =((length(primeFactors n)) == 1)

-- this approach was very slow!
	
--primeSums :: Integer -> [ (Integer, Maybe Int) ]
--primeSums x = primeSumsInternal $ takeWhile (<x) primes
--	where 
--		primeSumsInternal :: [Integer] -> [ (Integer, Maybe Int) ]
--		primeSumsInternal [] = []
--		primeSumsInternal (x:xs) = [(n,a)| n<-(x:xs), let a = n `elemIndex` (scanl (+) 0 (takeWhile (<n) xs)), a /= Nothing] ++ primeSumsInternal xs
	
--euler_050 =  fst $ maximumBy (comparing snd) (primeSums 1000000)

primesUnder1Million = takeWhile (<1000000) primes

numPrimes = toInteger(length primesUnder1Million )



-- Adds a list together until a limit is exceeded. Returns the total (just prior to the limit) and those elements of the list which were added (in reverse order)

-- this takes a few arguments:
-- limit, is the number below which the consecutive sequence must sum
-- s is the current value of the sums
-- x:xs is the list of things to be added up
-- y:ys is the list of things which have been added
sumSeq :: Integral a => a -> a -> [a] -> [a] -> (a, [a])
sumSeq limit n [] ys = (n, ys)
sumSeq limit n (x:xs) ys
	|	s >= limit	 	 = (n, ys)
	|	otherwise 		 = sumSeq limit s xs (x:ys)
	where
		s = n + x

-- Takes a value and a list. Subtracts each list element in turn until the value is prime. Returns the value and the number of elements remaining in the list.
		
sumSeqMaxPrimes :: Integer -> [Integer] -> Integer -> [[Integer]]
sumSeqMaxPrimes _ [] _ = []
sumSeqMaxPrimes limit (x:xs) currentMax = 
	if thisValue == [0,0] then nextValues else thisValue : nextValues
		where 
			thisValue = maxPrime ( sumSeq limit 0 (x:xs) [] ) currentMax
			nextValues = sumSeqMaxPrimes limit xs (max currentMax ( thisValue!!1))
			maxPrime :: (Integer,[Integer]) -> Integer -> [Integer]
			maxPrime (n, []) _ 		= [n, 0]
			maxPrime (n, (x:xs)) newMax
				|	listLength < newMax = [0,0]
				|	isPrime n = [n,  listLength + 1]
				|	otherwise = maxPrime ((n-x),xs) newMax
				where
					listLength = toInteger(length xs)
				
euler_050 = head $ maximumBy (comparing (!!2)) $ sumSeqMaxPrimes 100 (takeWhile (<100) primes)
			